package main

import (
	"fmt"
	"math/rand"
)

// 定义跳跃表的节点
type Node struct {
	value   int     // 节点的值
	forward []*Node // 指向下一层节点的指针
}

// 定义跳跃表
type SkipList struct {
	head  *Node // 跳跃表的头节点
	level int   // 当前的最大层数
}

// 创建新的跳跃表
func NewSkipList(maxLevel int) *SkipList {
	// 创建头节点，初始值为负无穷大
	head := &Node{
		value:   -1,
		forward: make([]*Node, maxLevel),
	}
	return &SkipList{
		head:  head,
		level: 0,
	}
}

// 随机生成层数
func randomLevel(maxLevel int) int {
	level := 1
	for rand.Float32() < 0.5 && level < maxLevel {
		level++
	}
	return level
}

// 插入值到跳跃表
func (list *SkipList) Insert(value int) {
	update := make([]*Node, list.level+1) // 用于存储每层的前驱节点
	current := list.head

	// 从最高层开始查找插入位置
	for i := list.level; i >= 0; i-- {
		// 遍历当前层，找到插入位置
		for current.forward[i] != nil && current.forward[i].value < value {
			current = current.forward[i]
		}
		update[i] = current // 记录前驱节点
	}

	// 检查是否存在相同的值
	if current.forward[0] != nil && current.forward[0].value == value {
		return // 值已存在，不插入
	}

	// 随机生成新节点的层数
	newLevel := randomLevel(16)
	if newLevel > list.level {
		for i := list.level + 1; i <= newLevel; i++ {
			update = append(update, list.head) // 更新前驱节点为头节点
		}
		list.level = newLevel // 更新跳跃表的最大层数
	}

	// 创建新节点
	newNode := &Node{
		value:   value,
		forward: make([]*Node, newLevel+1),
	}

	// 插入新节点
	for i := 0; i <= newLevel; i++ {
		if i < len(update) { // 确保不超出范围
			newNode.forward[i] = update[i].forward[i] // 设置新节点的指针
			update[i].forward[i] = newNode            // 更新前驱节点的指针
		}
	}
}

// 查找值在跳跃表中
func (list *SkipList) Search(value int) bool {
	current := list.head

	// 从最高层开始查找
	for i := list.level; i >= 0; i-- {
		// 遍历当前层，查找目标值
		for current.forward[i] != nil && current.forward[i].value < value {
			current = current.forward[i]
		}
	}

	// 检查当前节点的下一个节点是否为目标值
	if current.forward[0] != nil && current.forward[0].value == value {
		return true // 找到值
	}
	return false // 未找到值
}

// 删除值从跳跃表
func (list *SkipList) Delete(value int) {
	update := make([]*Node, list.level+1)
	current := list.head

	// 从最高层开始查找
	for i := list.level; i >= 0; i-- {
		// 遍历当前层，查找目标值
		for current.forward[i] != nil && current.forward[i].value < value {
			current = current.forward[i]
		}
		update[i] = current // 记录前驱节点
	}

	// 检查是否存在相同的值
	if current.forward[0] == nil || current.forward[0].value != value {
		return // 值不存在，无法删除
	}

	// 删除节点
	for i := 0; i <= list.level; i++ {
		if i >= len(update) || i >= len(update[i].forward) || i >= len(current.forward) {
			continue
		}
		if update[i].forward[i] == current.forward[i] { // 确保不超出范围
			if current.forward[i] != nil { // 确保当前节点的下一个节点不为 nil
				update[i].forward[i] = current.forward[i].forward[i] // 更新前驱节点的指针
			}
		}
	}

	// 更新层数
	for list.level > 0 && list.head.forward[list.level] == nil {
		list.level-- // 降低层数
	}
}

// 打印跳跃表
func (list *SkipList) Print() {
	for i := list.level; i >= 0; i-- {
		current := list.head.forward[i]
		fmt.Printf("Level %d: ", i)
		for current != nil {
			fmt.Printf("%d ", current.value)
			current = current.forward[i]
		}
		fmt.Println()
	}
}

// 主函数
func main() {
	skipList := NewSkipList(16) // 创建跳跃表

	// 插入值
	skipList.Insert(3)
	skipList.Insert(6)
	skipList.Insert(7)
	skipList.Insert(9)
	skipList.Insert(12)
	skipList.Insert(19)

	// 打印跳跃表
	skipList.Print()

	// 查找值
	fmt.Println("Search 6:", skipList.Search(6))   // 输出: true
	fmt.Println("Search 15:", skipList.Search(15)) // 输出: false

	// 删除值
	skipList.Delete(6)
	fmt.Println("After deleting 6:")
	skipList.Print()
}
